//题目链接：https://leetcode.cn/problems/add-two-numbers/

//逆序的链表
// 5 -> 4 -> 3
// 4 -> 7 -> 6 -> 7 

//  345
// 7674

//直接逆序相加即可，记录进位

class Solution 
{
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) 
    {
        //1. 逆序直接相加即可
        //2. 将结果的个位存储到节点中，进位交给下一次计算
        //3. 有一个链表为空时，不再进入计算
        int carry=0;//进位
        ListNode newhead(-1);
        ListNode* tail=&newhead;
        ListNode* cur1=l1,*cur2=l2;
        while(cur1 || cur2 || carry)
        {
            int sum=0;
            if(cur1)//cur1不为空
            {
                sum+=cur1->val;
                cur1=cur1->next;
            }
            if(cur2)//cur2
            {
                sum+=cur2->val;
                cur2=cur2->next;
            }
            sum+=carry;
            int one_place=sum%10;
            //将和的个位取出，创建新节点尾插
            tail->next=new ListNode(one_place);
            tail=tail->next;
            //更新进位
            carry=sum/10;
        }
        return newhead.next;
    }
};